
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */
/* 590. N 叉树的后序遍历 */
/**
 * @param {Node|null} root
 * @return {number[]}
 */
/* 递归 */
var postorder = function (root) {
    const res = []
    helper(root, res)
    return res
};
const helper = (root, res) => {
    if (!root) return
    for (const c of root.children) {
        helper(c, res)
    }
    /* 后续遍历 */
    res.push(root.val)
}

/* 迭代 */
var postorder = function (root) {
    const res = []
    if (root == null) return res
    const stack = []
    stack.push(root)

    while (stack.length) {
        const node = stack.pop()
        if (node instanceof Node) {
            stack.push(node.val)
            for (let i = node.children.length - 1; i >= 0; i--) {
                stack.push(node.children[i])
            }
        } else {
            res.push(node)
        }
    }

    return res
}

var postorder = function (root) {
    const res = [];
    if (root == null) {
        return res;
    }

    const stack = [];
    const visited = new Set();
    stack.push(root);
    while (stack.length) {
        const node = stack[stack.length - 1];
        /* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */
        if (node.children.length === 0 || visited.has(node)) {
            stack.pop();
            res.push(node.val);
            continue;
        }
        for (let i = node.children.length - 1; i >= 0; --i) {
            stack.push(node.children[i]);
        }
        visited.add(node);
    }
    return res;
};


/* 前序遍历进行反转 */

var postorder = function (root) {
    const res = []
    if (root == null) return
    const stack = []
    stack.push(root)

    while (stack.length) {
        const node = stack.pop()
        res.push(node.val)
        for (const value of node.children) {
            stack.push(value)
        }
    }
    res.reverse()
    return res

}
